package com.jinliang.think.tree;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

public class BinaryTree<T, N> extends Node {
    /**
     * 先序
     *
     * @param node
     */
    public static void preOrder(Node node) {
        if (node == null) {
            return;
        } else {
            //打因当前节点
            System.out.print(node.getValue());
            preOrder((Node) node.getLeft());
            preOrder((Node) node.getRight());
        }


    }

    /**
     * 中序遍历：先遍历左子树--->中子树--->右子树
     *
     * @param node
     */
    public static void inOrder(Node node) {
        if (node == null) {
            return;
        } else {
            //打因当前节点
            inOrder((Node) node.getLeft());
            System.out.print(node.getValue());
            inOrder((Node) node.getRight());
        }
    }

    /**
     * 非递归遍历二叉树：中序
     * 思路：引入一个堆结构容器（先进后出）
     * 步骤一：根节点先入栈
     * 步骤二：遍历该堆容器----目的--->访问节点
     * 访问节点的条件1：该节点的左子树为null--->可访问
     * 访问节点的条件2：该节点的左子树不为null但是左子树已被访问---->可访问
     * <p>
     * 访问节点A的后续操作-->A节点的右节点B不为空---->B入栈
     *
     * @param node
     */
    public static void traversalNotUseRecursion(Node<String, Node> node) {
        //初始化堆（先进后出）
        Stack<Node<String, Node>> stack = new Stack<>();
        stack.push(node);
        Node midNode = node;
        while (!stack.empty()) {
            Node<String, Node> peek = stack.peek();
            Node<String, Node> left = peek.getLeft();
            //左节点不为null---> 入堆
            if (!Objects.isNull(left)) {
                if (left.getIsVist()) {
                    popVistPush(stack);
                } else {
                    stack.push(left);
                }
            } else {
                popVistPush(stack);
            }
        }
    }

    private static void popVistPush(Stack<Node<String, Node>> stack) {
        Node<String, Node> pop = stack.pop();
        System.out.print(pop.getValue());
        pop.setIsVist(Boolean.TRUE);
        //右节点
        Node right = pop.getRight();
        if (right != null) {
            stack.push(right);
        }
    }

    /**
     * 层次遍历
     * 思路：引入一个栈容器（先进先出）----》 遍历栈
     * 步骤一：根节点如栈
     * 步骤二：遍历栈，pop一个元素A,--->左节点入栈 + 右节点入栈
     *
     * @param node
     */
    public static void levelRraversal(Node<String, Node> node) {
        //初始化栈容器（先进先出）
        LinkedBlockingQueue<Node<String, Node>> queue = new LinkedBlockingQueue<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node<String, Node> poll = queue.poll();
            System.out.print(poll.getValue());
            if (poll.getRight() != null) {
                queue.add(poll.getRight());
            }
            if (poll.getLeft() != null) {
                queue.add(poll.getLeft());
            }
        }
    }

    /**
     * 创建二茶树
     */
    private static int createTreeByRecursion(Node<String, Node> node, String[] treeNodes, int n) {
        if ("#".equals(treeNodes[n])) {
            return n + 1;
        }
        node.setValue(treeNodes[n]);
        node.setLeft(new Node());
        int left = createTreeByRecursion(node.getLeft(), treeNodes, n + 1);
        node.setRight(new Node());
        int right = createTreeByRecursion(node.getRight(), treeNodes, left);
        return right;
    }

    /**
     * 利用堆（先进后出）容器建立二叉树
     * @param node
     * @param treeNodes
     */
    private static void createTreeByRecursion(Node<String, Node> node, LinkedList<String> treeNodes) {
        if (treeNodes.isEmpty()) {
            return;
        }
        if ("#".equals(treeNodes.peek())) {
            treeNodes.poll();
            return;
        }
        node.setValue(treeNodes.poll());
        node.setLeft(new Node());
        createTreeByRecursion(node.getLeft(), treeNodes);
        node.setRight(new Node());
        createTreeByRecursion(node.getRight(), treeNodes);

    }
    public static BinaryTree<String, Node> createTreeByRecursion(String[] treeNodes) {
        BinaryTree<String, Node> root = new BinaryTree<>();
        createTreeByRecursion(root, treeNodes, 0);
        return root;
    }
    public static BinaryTree<String, Node> createTreeByRecursion(LinkedList<String> treeNodes) {
        BinaryTree<String, Node> root = new BinaryTree<>();
        createTreeByRecursion(root, treeNodes);
        return root;
    }

}
